import java.util.List;

public class Main {
    // 50、Pow(x,n)
    public double myPow(double x, int n) {
        // 递归 + 快速幂

        // 分情况进入 递归函数
        return n < 0 ? 1.0 / pow(x,-n) : pow(x,n);
    }

    public double pow(double x,int n) {
        // 使用 快速幂 的做法
        // 比如想要求 3的16次幂，就是求3的8次幂，进行3的8次幂*3的8次幂 -> 3的16次幂，以此类推求3的8次幂就是求3的4次幂，直到求3的0次幂
        // 由此可以的出 递归的结束条件为 n == 0
        if (n == 0) {
            return 1;
        }

        // 我们使用递归解决，坚信这个pow函数可以得到 n/2的次幂，并返回结果，不用去管怎样求的
        double tmp = pow(x,n/2);
        // 还有当n为奇数的时候，我们的到的tmp是一个偶数，那么我们就要多乘个x，来进行多加一次
        // 比如3的21次幂，得到的tmp就是 3的10次幂，最后返回的就是 tmp*tmp*x
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }


    // 24、两两交换链表中的节点
    // 时间复杂度均为O(N)
    // 空间复杂度：迭代O(1) 循环O(N)
    public ListNode swapPairs2(ListNode head) {
        // 使用 迭代(循环)
        ListNode newHead = new ListNode(0);// 哨兵位的头结点
        newHead.next = head;
        ListNode tmp = newHead;
        while(tmp.next != null && tmp.next.next != null) {
            ListNode cur1 = tmp.next;
            ListNode cur2 = tmp.next.next;

            tmp.next = cur2;
            cur1.next = cur2.next;
            cur2.next = cur1;

            // 更新tmp，这个时候 tmp 要更新到 tmp.next.next位置，这时候这个位置是 cur1了，而非cur2
            tmp = cur1;
        }

        return newHead.next;
    }
    public ListNode swapPairs(ListNode head) {
        // 使用递归解决

        // 我们每次交换 相邻的两个节点 ，那么这就是相同的子问题，函数会返回交换后的头结点
        // 比如 1->2 交换后 2 -> 1函数就会返回 2 这个节点的位置

        // 递归结束的条件
        if (head == null || head.next == null) {
            return head;
        }

        // 比如 1 -> 2 -> 3 -> 4
        //交换后 2 -> 1 -> 4 -> 3
        // 先是 2指向1，1指向4这个位置，最后2为头节点，函数会返回，3和4交换也是这个方式，就是相同的问题
        // 坚信这个 函数一定会把 前两个节点后面的所有节点进行两两交换，最后返回后面交换后的链表的头结点
        ListNode tmp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = tmp;

        return ret;
    }

    // 206、翻转链表
    public ListNode reverseList(ListNode head) {
        // 使用递归进行解决问题

        // 结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 我们每次的子问题都是把两个节点进行翻转，那么我们坚信 函数可以把head 后面的head.next开始的节点都可以进行翻转，
        // 并且返回一个头节点，就是反转后的头结点
        ListNode newHead = reverseList(head.next);
        // 比如 1 -> 2 ->null，1为head，2为head.next
        // 下面就是解决每一子问题的方式
        // 转换成 2 -> 1 -> null
        ListNode cur = head.next;
        cur.next = head;
        head.next = null;

        return newHead;
    }


    // 21、合并两个有序数组
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 使用递归的方式解决问题

        // 结束条件，当谁为null，返回另一个
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // 我们的这个重复的问题就是合并两个有序数组
        // 那么我们就是 每个问题都是 取一个小的数作为头，之后进行连接后面有序的数组
        // 最后再进行返回头结点
        // 不要管函数式如何把两个数组组成有序的，我们只需要找小的数作为头，连接后面有序的数组，这个就是解决了一个子问题，这就可以了
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }


    // 面试题08.06 汉诺塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        // 使用递归的方式

        // 这是一个重复的问题
        // 那么我们可以使用 递归的方式 来解决这个问题
        // 重复的子问题，就是 将a柱子上的一堆盘子，借助b，转移到c上
        // 可以抽象成下面的函数
        dfs(A,B,C,A.size());
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n) {
        // 我们在解决这个问题的时候呢，因为是重复的子问题
        // 我们只关系某一个子问题的解决方式就可以了，不用去管是如何实现的

        // 处理一下边界
        if (n == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }

        // 每个子问题都是这个步骤
        // 1、先把A中的n-1个盘子，借助C转移到B上
        dfs(A,C,B,n - 1);
        // 2、之后 A中剩余一个，将其转移到C上
        C.add(A.remove(A.size() - 1));
        // 3、把B(n-1个盘子)上面的所有的盘子，借助A移动到C上
        dfs(B,A,C,n - 1);

    }
}
